#include<iostream>
#include<assert.h>
using namespace std;

// 避免与库里面的冲突，用命名空间封装
namespace Wang
{

template<class T>
class vector
{
    T* _start = nullptr;          // 指向第一个元素
    T* _finish = nullptr;         // 指向最后一个元素的下一个元素
    T* _end_of_storage = nullptr; // 指向已分配内存的结尾
public:
    vector() = default;     // 强制编译器生成默认构造

    // 用n个x构造
    vector(size_t n, const T& x = T())
        :_start(new T[n])
        ,_finish(_start + n)
        ,_end_of_storage(_start + n)
    {
        T* i = _start;
        while(i != _finish)
        {
            *i = x;
            ++i;
        }
    }

    vector(int n, const T& x = T())
        :_start(new T[n])
        ,_finish(_start + n)
        ,_end_of_storage(_start + n)
    {
        T* i = _start;
        while(i != _finish)
        {
            *i = x;
            ++i;
        }
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
        while(first != last)
        {
            push_back(*first);
            ++first;
        }
    }

    // 用initializer_list构造
    vector(initializer_list<T> il)
    {
        reserve(il.size());
        for(auto& e : il)
            push_back(e);
    }

    // 拷贝构造。这种写法也可以：vector(const vector<T>& v)
    vector(const vector& v)
    {
        size_t n = v.size();
        _start = new T[n];
        _finish = _end_of_storage = _start + n;
        for(int i = 0; i < n; i++)
            _start[i] = v._start[i];
    }

    vector& operator= (const vector& v)
    {
        if(this != &v) // 避免自己给自己赋值
        {
            vector t(v);
            swap(t);
        }
        return *this;
    }

    // // vector<T> operator= (vector<T> v)
    // vector& operator= (vector v)
    // {
    //     swap(v);
    //     return *this;
    // }

    ~vector()
    {
        // cout << "~vector()" << endl;
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }

    size_t size() const { return _finish - _start; }
    size_t capacity() const { return _end_of_storage - _start; }
    bool empty() const { return _start == _finish; }

    // void swap(vector<T>& v)
    void swap(vector& v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_end_of_storage, v._end_of_storage);
    }

    typedef T* iterator;
    typedef const T* const_iterator;    // const迭代器应当是：可修改指向，不可修改指向的内容

    // begin()返回第一个元素的位置，end()返回最后一个元素的下一个元素的位置
    iterator begin() { return _start; }
    iterator end() { return _finish; }
    const_iterator begin() const { return _start; }
    const_iterator end() const { return _finish; }
    
    T& operator[](size_t pos) 
    { 
        assert(pos < size());
        return _start[pos]; 
    }
    const T& operator[](size_t pos) const 
    {
        assert(pos < size());
        return _start[pos]; 
    }
    T& front() 
    {
        assert(!empty());
        return _start[0];
    }
    const T& front() const
    {
        assert(!empty());
        return _start[0];
    }

    T& back() 
    {
        assert(!empty());
        return *(_finish - 1);
    }
    const T& back() const
    {
        assert(!empty());
        return *(_finish - 1);
    }

    void reserve(size_t n)
    {
        if(n > capacity())
        {
            T* tmp = new T[n];
            int sz = size();
            // 这里也不能用memcpy，需要用赋值
            for(int i = 0; i < sz; i++)
                tmp[i] = _start[i];
            delete[] _start;
            _start = tmp;
            _finish = _start + sz;
            _end_of_storage = _start + n;
        }
    }

    void resize(size_t n, const T& x = T())
    {
        size_t sz = size();
        if (n <= sz)
            _finish = _start + n;
        else
        {
            reserve(n);
            for (int i = sz; i < n; ++i)
                _start[i] = x;
            _finish = _start + n;
        }
    }
    void push_back(const T& x)
    {
        if(_finish == _end_of_storage)
            reserve(capacity() == 0 ? 4 : 2*capacity());
        *_finish = x;
        ++_finish;
    }

    void pop_back()
    {
        assert(_start != _finish); // 不为空
        --_finish;
    }

    // 扩容会使迭代器失效
    // 在pos位置插入x，返回值是指向第一个新插入元素的迭代器
    iterator insert(iterator pos, const T& x)
    {
        assert(pos >= begin() && pos <= end());
        int index = pos - begin(); 

        if(_finish == _end_of_storage)   
            reserve(capacity() == 0 ? 4 : 2*capacity());

        pos = begin() + index;
        for(iterator i = end(); i != pos; i--)
            *i = *(i - 1);
        *pos = x;
        ++_finish;
        return pos;
    }

    // 删除pos指向的元素。返回值是一个迭代器，指向被移除元素之后的那个元素
    iterator erase(iterator pos)
    {
        assert(pos >= begin() && pos < end());
        for(iterator i = pos; i != end() - 1; i++)
            *i = *(i + 1);
        --_finish;
        return pos;
    }

    void clear() { _finish = _start; }
};

} // namespace Wang